<!Doctype html>
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
	<meta name="viewport" content="width=device-width, initial-scale=1.0" />
	<title>1.10 基数排序 | 菜鸟教程</title>

  <meta name='robots' content='max-image-preview:large' />
<link rel='stylesheet' id='classic-theme-styles-css' href='../0/classic-themes.min.css?ver=6.2' type='text/css' media='all' />
<link rel="canonical" href="../w3cnote/radix-sort.html" />
<meta name="keywords" content="1.10 基数排序">
<meta name="description" content="基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。 1. 基数排序 vs 计数排序 vs 桶排序  基数排序有两种方法： 这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：  基数排序：根据键值的每位数字来分配桶； 计数排序：每个桶只存储单一键值； 桶排序：每个桶存储一定范围的数值；..">
		
	<link rel="shortcut icon" href="https://static.runoob.com/images/favicon.ico">
	<link rel="stylesheet" href="../0/style.css?v=1.170" type="text/css" media="all" />	
	<link rel="stylesheet" href="../0/font-awesome.min.css" media="all" />	
  <!--[if gte IE 9]><!-->
  <script src=""></script>
  <!--<![endif]-->
  <!--[if lt IE 9]>
     <script src=""></script>
     <script src=""></script>
  <![endif]-->
  <link rel="apple-touch-icon" href="https://static.runoob.com/images/icon/mobile-icon.png"/>
  <meta name="apple-mobile-web-app-title" content="菜鸟教程">
</head>
<body>

<!--  头部 -->
<div class="container logo-search">

  <div class="col search row-search-mobile">
    <form action="index.php">
      <input class="placeholder" placeholder="搜索……" name="s" autocomplete="off">
      
    </form>
  </div>

  <div class="row">
    <div class="col logo">
      <h1><a href="../">菜鸟教程 -- 学的不仅是技术，更是梦想！</a></h1>
    </div>
        <div class="col right-list"> 
    <button class="btn btn-responsive-nav btn-inverse" data-toggle="collapse" data-target=".nav-main-collapse" id="pull" style=""> <i class="fa fa-navicon"></i> </button>
    </div>
        
    <div class="col search search-desktop last">
      <div class="search-input" >
      <form action="//www.runoob.com/" target="_blank">
        <input class="placeholder" id="s" name="s" placeholder="搜索……"  autocomplete="off" style="height: 44px;">
      </form>
      
      </div>
    </div>
  </div>
</div>



<!-- 导航栏 -->
<div class="container navigation">
    <div class="row">
        <div class="col nav">
            

                        <ul class="pc-nav" id="note-nav">
                <li><a href="../">首页</a></li>
                <li><a href="../w3cnote">笔记首页</a></li>
                <li><a href="../w3cnote/android-tutorial-intro.html" title="Android 基础入门教程">Android</a></li>
                <li><a href="../w3cnote/es6-tutorial.html" title="ES6 教程">ES6 教程</a></li>
                <li><a href="../w3cnote/ten-sorting-algorithm.html" title="排序算法">排序算法</a></li>
                <li><a href="../w3cnote/hadoop-tutorial.html" title="Hadoop 教程">Hadoop</a></li>
                <li><a href="../w3cnote/zookeeper-tutorial.html" title="Zookeeper 教程">Zookeeper</a></li>
                <li><a href="../w3cnote/verilog-tutorial.html" title="Verilog 教程">Verilog</a></li>
                <li><a href="../w3cnote_genre/code" title="编程技术">编程技术</a></li> 
                <li><a href="../w3cnote_genre/coderlife" title="程序员人生">程序员人生</a></li>
                
                <!--<li><a href="javascript:;" class="runoob-pop">登录</a></li>
                
                
                        <li>
                <a style="font-weight:bold;" href="../linux/linux-tutorial.html#yunserver" target="_blank" onclick="_hmt.push(['_trackEvent', 'aliyun', 'click', 'aliyun'])" title="kkb">云服务器</a>
                </li>
                <li><a href="http://gk.link/a/104mQ" target="_blank" style="font-weight: bold;"onclick="_hmt.push(['_trackEvent', '极客时间', 'click', 'jike'])" title="我的圈子">极客时间</a></li>
            
                
                <li><a target="_blank" href="../shoppinglist" rel="nofollow">知识店铺</a></li> 
        -->
            </ul>
                        
              
            <ul class="mobile-nav">
                <li><a href="../w3cnote">首页</a></li>
                <li><a href="../w3cnote_genre/android" target="_blank" title="Android 基础入门教程">Android</a></li>
                <li><a href="../w3cnote/es6-tutorial.html" target="_blank" title="ES6 教程">ES6</a></li>
                <li><a href="../w3cnote_genre/joke" target="_blank" title="程序员笑话">逗乐</a></li>
                
                <a href="javascript:void(0)" class="search-reveal">Search</a> 
            </ul>
            
        </div>
    </div>
</div>


<!--  内容  -->
<div class="container main">
	<div class="row">

		<div class="col middle-column big-middle-column">
	 			<div class="article">
			<div class="article-heading">
				<h2>1.10 基数排序</h2>				<h3><em>分类</em> <a href="../w3cnote_genre/algorithm" title="算法" >算法</a> </h3>
			</div>
			<div class="article-body note-body">
				<div class="article-intro">
					<p>基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。</p>
<h3>1. 基数排序 vs 计数排序 vs 桶排序</h3>

<p>基数排序有两种方法：</p>
<p>这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：</p>
<ul>
<li>基数排序：根据键值的每位数字来分配桶；</li>
<li>计数排序：每个桶只存储单一键值；</li>
<li>桶排序：每个桶存储一定范围的数值；</li>
</ul>

<h3>2. LSD 基数排序动图演示</h3>

<p><img decoding="async" src="//www.runoob.com/wp-content/uploads/2019/03/radixSort.gif" alt="" /></p>

<hr>
<h2>代码实现</h2>
<h3>JavaScript</h3>

<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #006600; font-style: italic;">//LSD Radix Sort</span><br />
<span style="color: #000066; font-weight: bold;">var</span> counter <span style="color: #339933;">=</span> <span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
<span style="color: #000066; font-weight: bold;">function</span> radixSort<span style="color: #009900;">&#40;</span>arr<span style="color: #339933;">,</span> maxDigit<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> mod <span style="color: #339933;">=</span> <span style="color: #CC0000;">10</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> dev <span style="color: #339933;">=</span> <span style="color: #CC0000;">1</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">var</span> i <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> maxDigit<span style="color: #339933;">;</span> i<span style="color: #339933;">++,</span> dev <span style="color: #339933;">*=</span> <span style="color: #CC0000;">10</span><span style="color: #339933;">,</span> mod <span style="color: #339933;">*=</span> <span style="color: #CC0000;">10</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span><span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">var</span> j <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span> j <span style="color: #339933;">&lt;</span> arr.<span style="color: #660066;">length</span><span style="color: #339933;">;</span> j<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> bucket <span style="color: #339933;">=</span> parseInt<span style="color: #009900;">&#40;</span><span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>j<span style="color: #009900;">&#93;</span> <span style="color: #339933;">%</span> mod<span style="color: #009900;">&#41;</span> <span style="color: #339933;">/</span> dev<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">if</span><span style="color: #009900;">&#40;</span>counter<span style="color: #009900;">&#91;</span>bucket<span style="color: #009900;">&#93;</span><span style="color: #339933;">==</span><span style="color: #003366; font-weight: bold;">null</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter<span style="color: #009900;">&#91;</span>bucket<span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> <span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter<span style="color: #009900;">&#91;</span>bucket<span style="color: #009900;">&#93;</span>.<span style="color: #660066;">push</span><span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>j<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> pos <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">for</span><span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">var</span> j <span style="color: #339933;">=</span> <span style="color: #CC0000;">0</span><span style="color: #339933;">;</span> j <span style="color: #339933;">&lt;</span> counter.<span style="color: #660066;">length</span><span style="color: #339933;">;</span> j<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">var</span> value <span style="color: #339933;">=</span> <span style="color: #003366; font-weight: bold;">null</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">if</span><span style="color: #009900;">&#40;</span>counter<span style="color: #009900;">&#91;</span>j<span style="color: #009900;">&#93;</span><span style="color: #339933;">!=</span><span style="color: #003366; font-weight: bold;">null</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while <span style="color: #009900;">&#40;</span><span style="color: #009900;">&#40;</span>value <span style="color: #339933;">=</span> counter<span style="color: #009900;">&#91;</span>j<span style="color: #009900;">&#93;</span>.<span style="color: #660066;">shift</span><span style="color: #009900;">&#40;</span><span style="color: #009900;">&#41;</span><span style="color: #009900;">&#41;</span> <span style="color: #339933;">!=</span> <span style="color: #003366; font-weight: bold;">null</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr<span style="color: #009900;">&#91;</span>pos<span style="color: #339933;">++</span><span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
<span style="color: #009900;">&#125;</span><br />
</div></div>

<h3>Java</h3>

<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #008000; font-style: italic; font-weight: bold;">/**<br />
&nbsp;* 基数排序<br />
&nbsp;* 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9<br />
&nbsp;*/</span><br />
<span style="color: #000000; font-weight: bold;">public</span> <span style="color: #000000; font-weight: bold;">class</span> RadixSort <span style="color: #000000; font-weight: bold;">implements</span> IArraySort <span style="color: #009900;">&#123;</span><br />
<br />
&nbsp; &nbsp; @Override<br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">public</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> sort<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> sourceArray<span style="color: #009900;">&#41;</span> <span style="color: #000000; font-weight: bold;">throws</span> <span style="color: #003399;">Exception</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #666666; font-style: italic;">// 对 arr 进行拷贝，不改变参数内容</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr <span style="color: #339933;">=</span> <span style="color: #003399;">Arrays</span>.<span style="color: #006633;">copyOf</span><span style="color: #009900;">&#40;</span>sourceArray, sourceArray.<span style="color: #006633;">length</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> maxDigit <span style="color: #339933;">=</span> getMaxDigit<span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> radixSort<span style="color: #009900;">&#40;</span>arr, maxDigit<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #008000; font-style: italic; font-weight: bold;">/**<br />
&nbsp; &nbsp; &nbsp;* 获取最高位数<br />
&nbsp; &nbsp; &nbsp;*/</span><br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">private</span> <span style="color: #000066; font-weight: bold;">int</span> getMaxDigit<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> maxValue <span style="color: #339933;">=</span> getMaxValue<span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> getNumLenght<span style="color: #009900;">&#40;</span>maxValue<span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">private</span> <span style="color: #000066; font-weight: bold;">int</span> getMaxValue<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> maxValue <span style="color: #339933;">=</span> arr<span style="color: #009900;">&#91;</span><span style="color: #cc66cc;">0</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span> value <span style="color: #339933;">:</span> arr<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>maxValue <span style="color: #339933;">&lt;</span> value<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxValue <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> maxValue<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">protected</span> <span style="color: #000066; font-weight: bold;">int</span> getNumLenght<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">long</span> num<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">if</span> <span style="color: #009900;">&#40;</span>num <span style="color: #339933;">==</span> <span style="color: #cc66cc;">0</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> <span style="color: #cc66cc;">1</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> lenght <span style="color: #339933;">=</span> <span style="color: #cc66cc;">0</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">long</span> temp <span style="color: #339933;">=</span> num<span style="color: #339933;">;</span> temp <span style="color: #339933;">!=</span> <span style="color: #cc66cc;">0</span><span style="color: #339933;">;</span> temp <span style="color: #339933;">/=</span> <span style="color: #cc66cc;">10</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lenght<span style="color: #339933;">++;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> lenght<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">private</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> radixSort<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr, <span style="color: #000066; font-weight: bold;">int</span> maxDigit<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> mod <span style="color: #339933;">=</span> <span style="color: #cc66cc;">10</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> dev <span style="color: #339933;">=</span> <span style="color: #cc66cc;">1</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span> i <span style="color: #339933;">=</span> <span style="color: #cc66cc;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> maxDigit<span style="color: #339933;">;</span> i<span style="color: #339933;">++</span>, dev <span style="color: #339933;">*=</span> <span style="color: #cc66cc;">10</span>, mod <span style="color: #339933;">*=</span> <span style="color: #cc66cc;">10</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #666666; font-style: italic;">// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> counter <span style="color: #339933;">=</span> <span style="color: #000000; font-weight: bold;">new</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span>mod <span style="color: #339933;">*</span> <span style="color: #cc66cc;">2</span><span style="color: #009900;">&#93;</span><span style="color: #009900;">&#91;</span><span style="color: #cc66cc;">0</span><span style="color: #009900;">&#93;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span> j <span style="color: #339933;">=</span> <span style="color: #cc66cc;">0</span><span style="color: #339933;">;</span> j <span style="color: #339933;">&lt;</span> arr.<span style="color: #006633;">length</span><span style="color: #339933;">;</span> j<span style="color: #339933;">++</span><span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> bucket <span style="color: #339933;">=</span> <span style="color: #009900;">&#40;</span><span style="color: #009900;">&#40;</span>arr<span style="color: #009900;">&#91;</span>j<span style="color: #009900;">&#93;</span> <span style="color: #339933;">%</span> mod<span style="color: #009900;">&#41;</span> <span style="color: #339933;">/</span> dev<span style="color: #009900;">&#41;</span> <span style="color: #339933;">+</span> mod<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter<span style="color: #009900;">&#91;</span>bucket<span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> arrayAppend<span style="color: #009900;">&#40;</span>counter<span style="color: #009900;">&#91;</span>bucket<span style="color: #009900;">&#93;</span>, arr<span style="color: #009900;">&#91;</span>j<span style="color: #009900;">&#93;</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000066; font-weight: bold;">int</span> pos <span style="color: #339933;">=</span> <span style="color: #cc66cc;">0</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> bucket <span style="color: #339933;">:</span> counter<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">for</span> <span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span> value <span style="color: #339933;">:</span> bucket<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr<span style="color: #009900;">&#91;</span>pos<span style="color: #339933;">++</span><span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #008000; font-style: italic; font-weight: bold;">/**<br />
&nbsp; &nbsp; &nbsp;* 自动扩容，并保存数据<br />
&nbsp; &nbsp; &nbsp;*<br />
&nbsp; &nbsp; &nbsp;* @param arr<br />
&nbsp; &nbsp; &nbsp;* @param value<br />
&nbsp; &nbsp; &nbsp;*/</span><br />
&nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">private</span> <span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arrayAppend<span style="color: #009900;">&#40;</span><span style="color: #000066; font-weight: bold;">int</span><span style="color: #009900;">&#91;</span><span style="color: #009900;">&#93;</span> arr, <span style="color: #000066; font-weight: bold;">int</span> value<span style="color: #009900;">&#41;</span> <span style="color: #009900;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; arr <span style="color: #339933;">=</span> <span style="color: #003399;">Arrays</span>.<span style="color: #006633;">copyOf</span><span style="color: #009900;">&#40;</span>arr, arr.<span style="color: #006633;">length</span> <span style="color: #339933;">+</span> <span style="color: #cc66cc;">1</span><span style="color: #009900;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; arr<span style="color: #009900;">&#91;</span>arr.<span style="color: #006633;">length</span> <span style="color: #339933;">-</span> <span style="color: #cc66cc;">1</span><span style="color: #009900;">&#93;</span> <span style="color: #339933;">=</span> value<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000; font-weight: bold;">return</span> arr<span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #009900;">&#125;</span><br />
<span style="color: #009900;">&#125;</span><br />
</div></div>

<h3>PHP</h3>
<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #000000; ">function</span> radixSort<span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #000000;">,</span> <span style="color: #05a;">$maxDigit</span> <span style="color: #000000;">=</span> <span style="color: #164; font-weight: bold;">null</span><span style="color: #164;">&#41;</span><br />
<span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #708;">if</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$maxDigit</span> <span style="color: #000000;">===</span> <span style="color: #164; font-weight: bold;">null</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$maxDigit</span> <span style="color: #000000;">=</span> <span style="color: #990000;">max</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">$counter</span> <span style="color: #000000;">=</span> <span style="color: #164;">&#91;</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$i</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span> <span style="color: #000000;">&lt;</span> <span style="color: #05a;">$maxDigit</span><span style="color: #000000;">;</span> <span style="color: #05a;">$i</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$j</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span> <span style="color: #05a;">$j</span> <span style="color: #000000;">&lt;</span> <span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$arr</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span> <span style="color: #05a;">$j</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #990000;">preg_match_all</span><span style="color: #164;">&#40;</span><span style="color: #a11;">'/\d/'</span><span style="color: #000000;">,</span> <span style="color: #164;">&#40;</span>string<span style="color: #164;">&#41;</span> <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$j</span><span style="color: #164;">&#93;</span><span style="color: #000000;">,</span> <span style="color: #05a;">$matches</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$numArr</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$matches</span><span style="color: #164;">&#91;</span><span style="color: #164;">0</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$lenTmp</span> <span style="color: #000000;">=</span> <span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$numArr</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$bucket</span> <span style="color: #000000;">=</span> <span style="color: #990000;">array_key_exists</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$lenTmp</span> <span style="color: #000000;">-</span> <span style="color: #05a;">$i</span> <span style="color: #000000;">-</span> <span style="color: #164;">1</span><span style="color: #000000;">,</span> <span style="color: #05a;">$numArr</span><span style="color: #164;">&#41;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ? <span style="color: #990000;">intval</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$numArr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$lenTmp</span> <span style="color: #000000;">-</span> <span style="color: #05a;">$i</span> <span style="color: #000000;">-</span> <span style="color: #164;">1</span><span style="color: #164;">&#93;</span><span style="color: #164;">&#41;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000000;">:</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #708;">if</span> <span style="color: #164;">&#40;</span><span style="color: #000000;">!</span><span style="color: #990000;">array_key_exists</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$bucket</span><span style="color: #000000;">,</span> <span style="color: #05a;">$counter</span><span style="color: #164;">&#41;</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$counter</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$bucket</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">=</span> <span style="color: #164;">&#91;</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$counter</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$bucket</span><span style="color: #164;">&#93;</span><span style="color: #164;">&#91;</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$j</span><span style="color: #164;">&#93;</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$pos</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$j</span> <span style="color: #000000;">=</span> <span style="color: #164;">0</span><span style="color: #000000;">;</span> <span style="color: #05a;">$j</span> <span style="color: #000000;">&lt;</span> <span style="color: #990000;">count</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$counter</span><span style="color: #164;">&#41;</span><span style="color: #000000;">;</span> <span style="color: #05a;">$j</span><span style="color: #000000;">++</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$value</span> <span style="color: #000000;">=</span> <span style="color: #164; font-weight: bold;">null</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #708;">if</span> <span style="color: #164;">&#40;</span><span style="color: #05a;">$counter</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$j</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">!==</span> <span style="color: #164; font-weight: bold;">null</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #708;">while</span> <span style="color: #164;">&#40;</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$value</span> <span style="color: #000000;">=</span> <span style="color: #990000;">array_shift</span><span style="color: #164;">&#40;</span><span style="color: #05a;">$counter</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$j</span><span style="color: #164;">&#93;</span><span style="color: #164;">&#41;</span><span style="color: #164;">&#41;</span> <span style="color: #000000;">!==</span> <span style="color: #164; font-weight: bold;">null</span><span style="color: #164;">&#41;</span> <span style="color: #164;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">$arr</span><span style="color: #164;">&#91;</span><span style="color: #05a;">$pos</span><span style="color: #000000;">++</span><span style="color: #164;">&#93;</span> <span style="color: #000000;">=</span> <span style="color: #05a;">$value</span><span style="color: #000000;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #164;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #708;">return</span> <span style="color: #05a;">$arr</span><span style="color: #000000;">;</span><br />
<span style="color: #164;">&#125;</span><br />
</div></div>

<h3>C++</h3>
<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #05a;">int</span> maxbit<span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> data<span style="color: #008000;">&#91;</span><span style="color: #008000;">&#93;</span>, <span style="color: #05a;">int</span> n<span style="color: #008000;">&#41;</span> <span style="color: #666666;">//辅助函数，求数据的最大位数</span><br />
<span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> maxData <span style="color: #000080;">=</span> data<span style="color: #008000;">&#91;</span><span style="color: #0000dd;">0</span><span style="color: #008000;">&#93;</span><span style="color: #008080;">;</span>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #666666;">///&lt; 最大数</span><br />
&nbsp; &nbsp; <span style="color: #666666;">/// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。</span><br />
&nbsp; &nbsp; <span style="color: #05a;">for</span> <span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> i <span style="color: #000080;">=</span> <span style="color: #0000dd;">1</span><span style="color: #008080;">;</span> i <span style="color: #000080;">&lt;</span> n<span style="color: #008080;">;</span> <span style="color: #000040;">++</span>i<span style="color: #008000;">&#41;</span><br />
&nbsp; &nbsp; <span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">if</span> <span style="color: #008000;">&#40;</span>maxData <span style="color: #000080;">&lt;</span> data<span style="color: #008000;">&#91;</span>i<span style="color: #008000;">&#93;</span><span style="color: #008000;">&#41;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxData <span style="color: #000080;">=</span> data<span style="color: #008000;">&#91;</span>i<span style="color: #008000;">&#93;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> d <span style="color: #000080;">=</span> <span style="color: #0000dd;">1</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> p <span style="color: #000080;">=</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">while</span> <span style="color: #008000;">&#40;</span>maxData <span style="color: #000080;">&gt;=</span> p<span style="color: #008000;">&#41;</span><br />
&nbsp; &nbsp; <span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #666666;">//p *= 10; // Maybe overflow</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; maxData <span style="color: #000040;">/</span><span style="color: #000080;">=</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #000040;">++</span>d<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">return</span> d<span style="color: #008080;">;</span><br />
<span style="color: #696969;; font-style: italic;">/* &nbsp; &nbsp;int d = 1; //保存最大的位数<br />
&nbsp; &nbsp; int p = 10;<br />
&nbsp; &nbsp; for(int i = 0; i &lt; n; ++i)<br />
&nbsp; &nbsp; {<br />
&nbsp; &nbsp; &nbsp; &nbsp; while(data[i] &gt;= p)<br />
&nbsp; &nbsp; &nbsp; &nbsp; {<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p *= 10;<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ++d;<br />
&nbsp; &nbsp; &nbsp; &nbsp; }<br />
&nbsp; &nbsp; }<br />
&nbsp; &nbsp; return d;*/</span><br />
<span style="color: #008000;">&#125;</span><br />
<span style="color: #05a;">void</span> radixsort<span style="color: #008000;">&#40;</span><span style="color: #05a;">int</span> data<span style="color: #008000;">&#91;</span><span style="color: #008000;">&#93;</span>, <span style="color: #05a;">int</span> n<span style="color: #008000;">&#41;</span> <span style="color: #666666;">//基数排序</span><br />
<span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> d <span style="color: #000080;">=</span> maxbit<span style="color: #008000;">&#40;</span>data, n<span style="color: #008000;">&#41;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> <span style="color: #000040;">*</span>tmp <span style="color: #000080;">=</span> <span style="color: #05a;">new</span> <span style="color: #05a;">int</span><span style="color: #008000;">&#91;</span>n<span style="color: #008000;">&#93;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> <span style="color: #000040;">*</span>count <span style="color: #000080;">=</span> <span style="color: #05a;">new</span> <span style="color: #05a;">int</span><span style="color: #008000;">&#91;</span><span style="color: #0000dd;">10</span><span style="color: #008000;">&#93;</span><span style="color: #008080;">;</span> <span style="color: #666666;">//计数器</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> i, j, k<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">int</span> radix <span style="color: #000080;">=</span> <span style="color: #0000dd;">1</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span>i <span style="color: #000080;">=</span> <span style="color: #0000dd;">1</span><span style="color: #008080;">;</span> i <span style="color: #000080;">&lt;=</span> d<span style="color: #008080;">;</span> i<span style="color: #000040;">++</span><span style="color: #008000;">&#41;</span> <span style="color: #666666;">//进行d次排序</span><br />
&nbsp; &nbsp; <span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span>j <span style="color: #000080;">=</span> <span style="color: #0000dd;">0</span><span style="color: #008080;">;</span> j <span style="color: #000080;">&lt;</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span> j<span style="color: #000040;">++</span><span style="color: #008000;">&#41;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span> <span style="color: #000080;">=</span> <span style="color: #0000dd;">0</span><span style="color: #008080;">;</span> <span style="color: #666666;">//每次分配前清空计数器</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span>j <span style="color: #000080;">=</span> <span style="color: #0000dd;">0</span><span style="color: #008080;">;</span> j <span style="color: #000080;">&lt;</span> n<span style="color: #008080;">;</span> j<span style="color: #000040;">++</span><span style="color: #008000;">&#41;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k <span style="color: #000080;">=</span> <span style="color: #008000;">&#40;</span>data<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span> <span style="color: #000040;">/</span> radix<span style="color: #008000;">&#41;</span> <span style="color: #000040;">%</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span> <span style="color: #666666;">//统计每个桶中的记录数</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count<span style="color: #008000;">&#91;</span>k<span style="color: #008000;">&#93;</span><span style="color: #000040;">++</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span>j <span style="color: #000080;">=</span> <span style="color: #0000dd;">1</span><span style="color: #008080;">;</span> j <span style="color: #000080;">&lt;</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span> j<span style="color: #000040;">++</span><span style="color: #008000;">&#41;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span> <span style="color: #000080;">=</span> count<span style="color: #008000;">&#91;</span>j <span style="color: #000040;">-</span> <span style="color: #0000dd;">1</span><span style="color: #008000;">&#93;</span> <span style="color: #000040;">+</span> count<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span><span style="color: #008080;">;</span> <span style="color: #666666;">//将tmp中的位置依次分配给每个桶</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span>j <span style="color: #000080;">=</span> n <span style="color: #000040;">-</span> <span style="color: #0000dd;">1</span><span style="color: #008080;">;</span> j <span style="color: #000080;">&gt;=</span> <span style="color: #0000dd;">0</span><span style="color: #008080;">;</span> j<span style="color: #000040;">--</span><span style="color: #008000;">&#41;</span> <span style="color: #666666;">//将所有桶中记录依次收集到tmp中</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; k <span style="color: #000080;">=</span> <span style="color: #008000;">&#40;</span>data<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span> <span style="color: #000040;">/</span> radix<span style="color: #008000;">&#41;</span> <span style="color: #000040;">%</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tmp<span style="color: #008000;">&#91;</span>count<span style="color: #008000;">&#91;</span>k<span style="color: #008000;">&#93;</span> <span style="color: #000040;">-</span> <span style="color: #0000dd;">1</span><span style="color: #008000;">&#93;</span> <span style="color: #000080;">=</span> data<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count<span style="color: #008000;">&#91;</span>k<span style="color: #008000;">&#93;</span><span style="color: #000040;">--</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #05a;">for</span><span style="color: #008000;">&#40;</span>j <span style="color: #000080;">=</span> <span style="color: #0000dd;">0</span><span style="color: #008080;">;</span> j <span style="color: #000080;">&lt;</span> n<span style="color: #008080;">;</span> j<span style="color: #000040;">++</span><span style="color: #008000;">&#41;</span> <span style="color: #666666;">//将临时数组的内容复制到data中</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; data<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span> <span style="color: #000080;">=</span> tmp<span style="color: #008000;">&#91;</span>j<span style="color: #008000;">&#93;</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; radix <span style="color: #000080;">=</span> radix <span style="color: #000040;">*</span> <span style="color: #0000dd;">10</span><span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #008000;">&#125;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">delete</span> <span style="color: #008000;">&#91;</span><span style="color: #008000;">&#93;</span>tmp<span style="color: #008080;">;</span><br />
&nbsp; &nbsp; <span style="color: #05a;">delete</span> <span style="color: #008000;">&#91;</span><span style="color: #008000;">&#93;</span>count<span style="color: #008080;">;</span><br />
<span style="color: #008000;">&#125;</span><br />
</div></div>


<h3>C</h3>
<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #085;">#include&lt;stdio.h&gt;</span><br />
<span style="color: #085;">#define MAX 20</span><br />
<span style="color: #666666; font-style: italic;">//#define SHOWPASS</span><br />
<span style="color: #085;">#define BASE 10</span><br />
<br />
<span style="color: #993333;">void</span> print<span style="color: #000;">&#40;</span><span style="color: #993333;">int</span> <span style="color: #339933;">*</span>a<span style="color: #339933;">,</span> <span style="color: #993333;">int</span> n<span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; <span style="color: #993333;">int</span> i<span style="color: #339933;">;</span><br />
&nbsp; <span style="color: #708;">for</span> <span style="color: #000;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #164;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> n<span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #000066;">printf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;%d<span style="color: #000099; font-weight: bold;">\t</span>&quot;</span><span style="color: #339933;">,</span> a<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span><span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; <span style="color: #000;">&#125;</span><br />
<span style="color: #000;">&#125;</span><br />
<br />
<span style="color: #993333;">void</span> radixsort<span style="color: #000;">&#40;</span><span style="color: #993333;">int</span> <span style="color: #339933;">*</span>a<span style="color: #339933;">,</span> <span style="color: #993333;">int</span> n<span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; <span style="color: #993333;">int</span> i<span style="color: #339933;">,</span> b<span style="color: #000;">&#91;</span>MAX<span style="color: #000;">&#93;</span><span style="color: #339933;">,</span> m <span style="color: #339933;">=</span> a<span style="color: #000;">&#91;</span><span style="color: #164;">0</span><span style="color: #000;">&#93;</span><span style="color: #339933;">,</span> <span style="color: #000066;">exp</span> <span style="color: #339933;">=</span> <span style="color: #164;">1</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; <span style="color: #708;">for</span> <span style="color: #000;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #164;">1</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> n<span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #708;">if</span> <span style="color: #000;">&#40;</span>a<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span> <span style="color: #339933;">&gt;</span> m<span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; m <span style="color: #339933;">=</span> a<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000;">&#125;</span><br />
&nbsp; <span style="color: #000;">&#125;</span><br />
<br />
&nbsp; <span style="color: #708;">while</span> <span style="color: #000;">&#40;</span>m <span style="color: #339933;">/</span> <span style="color: #000066;">exp</span> <span style="color: #339933;">&gt;</span> <span style="color: #164;">0</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #993333;">int</span> bucket<span style="color: #000;">&#91;</span>BASE<span style="color: #000;">&#93;</span> <span style="color: #339933;">=</span> <span style="color: #000;">&#123;</span> <span style="color: #164;">0</span> <span style="color: #000;">&#125;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #000;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #164;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> n<span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; bucket<span style="color: #000;">&#91;</span><span style="color: #000;">&#40;</span>a<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span> <span style="color: #339933;">/</span> <span style="color: #000066;">exp</span><span style="color: #000;">&#41;</span> <span style="color: #339933;">%</span> BASE<span style="color: #000;">&#93;</span><span style="color: #339933;">++;</span><br />
&nbsp; &nbsp; <span style="color: #000;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #000;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #164;">1</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> BASE<span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; bucket<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span> <span style="color: #339933;">+=</span> bucket<span style="color: #000;">&#91;</span>i <span style="color: #339933;">-</span> <span style="color: #164;">1</span><span style="color: #000;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #000;">&#40;</span>i <span style="color: #339933;">=</span> n <span style="color: #339933;">-</span> <span style="color: #164;">1</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&gt;=</span> <span style="color: #164;">0</span><span style="color: #339933;">;</span> i<span style="color: #339933;">--</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; b<span style="color: #000;">&#91;</span><span style="color: #339933;">--</span>bucket<span style="color: #000;">&#91;</span><span style="color: #000;">&#40;</span>a<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span> <span style="color: #339933;">/</span> <span style="color: #000066;">exp</span><span style="color: #000;">&#41;</span> <span style="color: #339933;">%</span> BASE<span style="color: #000;">&#93;</span><span style="color: #000;">&#93;</span> <span style="color: #339933;">=</span> a<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #708;">for</span> <span style="color: #000;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #164;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> n<span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; &nbsp; a<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span> <span style="color: #339933;">=</span> b<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; <span style="color: #000;">&#125;</span><br />
<br />
&nbsp; &nbsp; <span style="color: #000066;">exp</span> <span style="color: #339933;">*=</span> BASE<span style="color: #339933;">;</span><br />
<br />
<span style="color: #085;">#ifdef SHOWPASS</span><br />
&nbsp; &nbsp; <span style="color: #000066;">printf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;<span style="color: #000099; font-weight: bold;">\n</span>PASS &nbsp; : &quot;</span><span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; &nbsp; print<span style="color: #000;">&#40;</span>a<span style="color: #339933;">,</span> n<span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
<span style="color: #085;">#endif</span><br />
&nbsp; <span style="color: #000;">&#125;</span><br />
<span style="color: #000;">&#125;</span><br />
<br />
<span style="color: #993333;">int</span> main<span style="color: #000;">&#40;</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; <span style="color: #993333;">int</span> arr<span style="color: #000;">&#91;</span>MAX<span style="color: #000;">&#93;</span><span style="color: #339933;">;</span><br />
&nbsp; <span style="color: #993333;">int</span> i<span style="color: #339933;">,</span> n<span style="color: #339933;">;</span><br />
<br />
&nbsp; <span style="color: #000066;">printf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;Enter total elements (n &lt;= %d) : &quot;</span><span style="color: #339933;">,</span> MAX<span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; <span style="color: #000066;">scanf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;%d&quot;</span><span style="color: #339933;">,</span> <span style="color: #339933;">&amp;</span>n<span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; n <span style="color: #339933;">=</span> n <span style="color: #339933;">&lt;</span> MAX <span style="color: #339933;">?</span> n <span style="color: #339933;">:</span> MAX<span style="color: #339933;">;</span><br />
<br />
&nbsp; <span style="color: #000066;">printf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;Enter %d Elements : &quot;</span><span style="color: #339933;">,</span> n<span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; <span style="color: #708;">for</span> <span style="color: #000;">&#40;</span>i <span style="color: #339933;">=</span> <span style="color: #164;">0</span><span style="color: #339933;">;</span> i <span style="color: #339933;">&lt;</span> n<span style="color: #339933;">;</span> i<span style="color: #339933;">++</span><span style="color: #000;">&#41;</span> <span style="color: #000;">&#123;</span><br />
&nbsp; &nbsp; <span style="color: #000066;">scanf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;%d&quot;</span><span style="color: #339933;">,</span> <span style="color: #339933;">&amp;</span>arr<span style="color: #000;">&#91;</span>i<span style="color: #000;">&#93;</span><span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; <span style="color: #000;">&#125;</span><br />
<br />
&nbsp; <span style="color: #000066;">printf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;<span style="color: #000099; font-weight: bold;">\n</span>ARRAY &nbsp;: &quot;</span><span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; print<span style="color: #000;">&#40;</span><span style="color: #339933;">&amp;</span>arr<span style="color: #000;">&#91;</span><span style="color: #164;">0</span><span style="color: #000;">&#93;</span><span style="color: #339933;">,</span> n<span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; radixsort<span style="color: #000;">&#40;</span><span style="color: #339933;">&amp;</span>arr<span style="color: #000;">&#91;</span><span style="color: #164;">0</span><span style="color: #000;">&#93;</span><span style="color: #339933;">,</span> n<span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; <span style="color: #000066;">printf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;<span style="color: #000099; font-weight: bold;">\n</span>SORTED : &quot;</span><span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; print<span style="color: #000;">&#40;</span><span style="color: #339933;">&amp;</span>arr<span style="color: #000;">&#91;</span><span style="color: #164;">0</span><span style="color: #000;">&#93;</span><span style="color: #339933;">,</span> n<span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
&nbsp; <span style="color: #000066;">printf</span><span style="color: #000;">&#40;</span><span style="color: #a11;">&quot;<span style="color: #000099; font-weight: bold;">\n</span>&quot;</span><span style="color: #000;">&#41;</span><span style="color: #339933;">;</span><br />
<br />
&nbsp; <span style="color: #708;">return</span> <span style="color: #164;">0</span><span style="color: #339933;">;</span><br />
<span style="color: #000;">&#125;</span><br />
</div></div>
<h3>Lua</h3>

<div class="example"><h2 class="example">实例</h2> <div class="example_code">
<span style="color: #a50; font-style: italic;">-- 获取表中位数</span><br />
<span style="color: Green; font-weight: bold;">local</span> maxBit <span style="color: #Gray;">=</span> <span style="color: Green; font-weight: bold;">function</span> <span style="color: Olive;">&#40;</span>tt<span style="color: Olive;">&#41;</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> weight <span style="color: #Gray;">=</span> <span style="color: Maroon;">10</span><span style="color: #Gray;">;</span> &nbsp; &nbsp; &nbsp;<span style="color: #a50; font-style: italic;">-- 十進制</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> bit <span style="color: #Gray;">=</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; <br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">for</span> k<span style="color: #Gray;">,</span> v <span style="color: Teal; font-weight: bold;">in</span> <span style="color: #05a;">pairs</span><span style="color: Olive;">&#40;</span>tt<span style="color: Olive;">&#41;</span> <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">while</span> v <span style="color: #Gray;">&gt;=</span> weight <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; weight <span style="color: #Gray;">=</span> weight <span style="color: #Gray;">*</span> <span style="color: Maroon;">10</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bit <span style="color: #Gray;">=</span> bit <span style="color: #Gray;">+</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">;</span> &nbsp;<br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">return</span> bit<span style="color: #Gray;">;</span><br />
<span style="color: Green; font-weight: bold;">end</span><br />
<span style="color: #a50; font-style: italic;">-- 基数排序</span><br />
<span style="color: Green; font-weight: bold;">local</span> radixSort <span style="color: #Gray;">=</span> <span style="color: Green; font-weight: bold;">function</span> <span style="color: Olive;">&#40;</span>tt<span style="color: Olive;">&#41;</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> maxbit <span style="color: #Gray;">=</span> maxBit<span style="color: Olive;">&#40;</span>tt<span style="color: Olive;">&#41;</span><span style="color: #Gray;">;</span> <br />
<br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> bucket <span style="color: #Gray;">=</span> <span style="color: Olive;">&#123;</span><span style="color: Olive;">&#125;</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> temp <span style="color: #Gray;">=</span> <span style="color: Olive;">&#123;</span><span style="color: Olive;">&#125;</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> radix <span style="color: #Gray;">=</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">for</span> i <span style="color: #Gray;">=</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">,</span> maxbit <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">for</span> j <span style="color: #Gray;">=</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">,</span> <span style="color: Maroon;">10</span> <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bucket<span style="color: Olive;">&#91;</span>j<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">=</span> <span style="color: Maroon;">0</span><span style="color: #Gray;">;</span> &nbsp; &nbsp; &nbsp;<span style="color: #a50; font-style: italic;">--- 清空桶</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">for</span> k<span style="color: #Gray;">,</span> v <span style="color: Teal; font-weight: bold;">in</span> <span style="color: #05a;">pairs</span><span style="color: Olive;">&#40;</span>tt<span style="color: Olive;">&#41;</span> <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> remainder <span style="color: #Gray;">=</span> <span style="color: #05a;">math.floor</span><span style="color: Olive;">&#40;</span><span style="color: Olive;">&#40;</span>v <span style="color: #Gray;">/</span> radix<span style="color: Olive;">&#41;</span><span style="color: Olive;">&#41;</span> <span style="color: #Gray;">%</span> <span style="color: Maroon;">10</span> <span style="color: #Gray;">+</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">;</span> &nbsp; &nbsp;<br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bucket<span style="color: Olive;">&#91;</span>remainder<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">=</span> bucket<span style="color: Olive;">&#91;</span>remainder<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">+</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">;</span> &nbsp; &nbsp; &nbsp;<span style="color: #a50; font-style: italic;">-- 每個桶數量自動增加1</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">for</span> j <span style="color: #Gray;">=</span> <span style="color: Maroon;">2</span><span style="color: #Gray;">,</span> <span style="color: Maroon;">10</span> <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bucket<span style="color: Olive;">&#91;</span>j<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">=</span> bucket<span style="color: Olive;">&#91;</span>j <span style="color: #Gray;">-</span> <span style="color: Maroon;">1</span><span style="color: Olive;">&#93;</span> <span style="color: #Gray;">+</span> bucket<span style="color: Olive;">&#91;</span>j<span style="color: Olive;">&#93;</span><span style="color: #Gray;">;</span> &nbsp;<span style="color: #a50; font-style: italic;">-- 每个桶的数量 = 以前桶数量和 + 自个数量</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span> <br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: #a50; font-style: italic;">-- 按照桶的位置，排序--这个是桶式排序，必须使用倒序，因为排序方法是从小到大，顺序下来，会出现大的在小的上面清空。</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">for</span> k <span style="color: #Gray;">=</span> <span style="color: #Gray;">#</span>tt<span style="color: #Gray;">,</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">,</span> <span style="color: #Gray;">-</span><span style="color: Maroon;">1</span> <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">local</span> remainder <span style="color: #Gray;">=</span> <span style="color: #05a;">math.floor</span><span style="color: Olive;">&#40;</span><span style="color: Olive;">&#40;</span>tt<span style="color: Olive;">&#91;</span>k<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">/</span> radix<span style="color: Olive;">&#41;</span><span style="color: Olive;">&#41;</span> <span style="color: #Gray;">%</span> <span style="color: Maroon;">10</span> <span style="color: #Gray;">+</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp<span style="color: Olive;">&#91;</span>bucket<span style="color: Olive;">&#91;</span>remainder<span style="color: Olive;">&#93;</span><span style="color: Olive;">&#93;</span> <span style="color: #Gray;">=</span> tt<span style="color: Olive;">&#91;</span>k<span style="color: Olive;">&#93;</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bucket<span style="color: Olive;">&#91;</span>remainder<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">=</span> bucket<span style="color: Olive;">&#91;</span>remainder<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">-</span> <span style="color: Maroon;">1</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">for</span> k<span style="color: #Gray;">,</span> v <span style="color: Teal; font-weight: bold;">in</span> <span style="color: #05a;">pairs</span><span style="color: Olive;">&#40;</span>temp<span style="color: Olive;">&#41;</span> <span style="color: Green; font-weight: bold;">do</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tt<span style="color: Olive;">&#91;</span>k<span style="color: Olive;">&#93;</span> <span style="color: #Gray;">=</span> v<span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span><br />
&nbsp; &nbsp; &nbsp; &nbsp; radix <span style="color: #Gray;">=</span> radix <span style="color: #Gray;">*</span> <span style="color: Maroon;">10</span><span style="color: #Gray;">;</span><br />
&nbsp; &nbsp; <span style="color: Green; font-weight: bold;">end</span><br />
<span style="color: Green; font-weight: bold;">end</span><span style="color: #Gray;">;</span><br />
</div></div>


<blockquote><p>参考地址：</p>
<p>https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md</p>
<p>https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F</p></blockquote>

				</div>
			</div>
			<div class="previous-next-links">
			<div class="previous-design-link">← <a href="../w3cnote/bucket-sort.html" rel="prev"> 1.9 桶排序</a> </div>
			<div class="next-design-link"></div>
			</div>
			<style>
.wrapper {
  /*text-transform: uppercase; */
  background: #ececec;
  color: #555;
  cursor: help;
  font-family: "Gill Sans", Impact, sans-serif;
  font-size: 20px;
  position: relative;
  text-align: center;
  width: 200px;
  -webkit-transform: translateZ(0); /* webkit flicker fix */
  -webkit-font-smoothing: antialiased; /* webkit text rendering fix */
}

.wrapper .tooltip {
  white-space: nowrap;
  font-size: 14px;
  text-align: left;
  background: #96b97d;
  bottom: 100%;
  color: #fff;
  display: block;
  left: -25px;
  margin-bottom: 15px;
  opacity: 0;
  padding: 14px;
  pointer-events: none;
  position: absolute;
  
  -webkit-transform: translateY(10px);
     -moz-transform: translateY(10px);
      -ms-transform: translateY(10px);
       -o-transform: translateY(10px);
          transform: translateY(10px);
  -webkit-transition: all .25s ease-out;
     -moz-transition: all .25s ease-out;
      -ms-transition: all .25s ease-out;
       -o-transition: all .25s ease-out;
          transition: all .25s ease-out;
  -webkit-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
     -moz-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
      -ms-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
       -o-box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
          box-shadow: 2px 2px 6px rgba(0, 0, 0, 0.28);
}
.tooltip a {
	color:#fff;
}
/* This bridges the gap so you can mouse into the tooltip without it disappearing */
.wrapper .tooltip:before {
  bottom: -20px;
  content: " ";
  display: block;
  height: 20px;
  left: 0;
  position: absolute;
  width: 100%;
}  

/* CSS Triangles - see Trevor's post */
.wrapper .tooltip:after {
  border-left: solid transparent 10px;
  border-right: solid transparent 10px;
  border-top: solid #96b97d 10px;
  bottom: -10px;
  content: " ";
  height: 0;
  left: 20%;
  margin-left: -13px;
  position: absolute;
  width: 0;
}
.wrapper .tooltip1 {
	margin-left: 50px;
	padding-top: 0px;
}
/*
.wrapper:hover .tooltip {
  opacity: 1;
  pointer-events: auto;
  -webkit-transform: translateY(0px);
     -moz-transform: translateY(0px);
      -ms-transform: translateY(0px);
       -o-transform: translateY(0px);
          transform: translateY(0px);
}
*/
/* IE can just show/hide with no transition */
.lte8 .wrapper .tooltip {
  display: none;
}

.lte8 .wrapper:hover .tooltip {
  display: block;
}

</style>

<link rel="stylesheet" href="../0/upvotejs.css">
<script src=""></script>
<script src=""></script>
<div class="title" id="comments">
	<h2 class="">
    <div class="altblock">
				<i style="font-size:28px;margin-top: 8px;" class="fa fa-plus-square" aria-hidden="true"></i>
		    </div>
    <span class="mw-headline" id="qa_headline">6  篇笔记</span>
	<span class="mw-headline" id="user_add_note" style="float:right;line-height: 62px;padding-right: 14px;"><i class="fa fa-pencil-square-o" aria-hidden="true"></i>  写笔记</span>
    </h2>
</div>

<div id="postcomments"  style="display:none;" >
	<ol class="commentlist">
		<li class="comment even thread-even depth-1" id="comment-57255"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;locenco</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;zha***hong1206@gmail.com</p></div><div id="runoobvote-id-57255" data-commid = "57255" class="upvotejs"><a class="upvote"></a> <span class="count">14</span></div></div><div class="comt-main" id="div-comment-57255"><p>java 代码里，mod 每次循环会乘 10，但 counter 的行数是不需要变的，能包含 [-9,9] 就可以了。</p>

<pre>for (int i = 0; i &lt; maxDigit; i++, dev *= 10, mod *= 10) {
        // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
    int[][] counter = new int[20][0];

    for (int j = 0; j &lt; arr.length; j++) {
        int bucket = ((arr[j] % mod) / dev) + 10;
        counter[bucket] = arrayAppend(counter[bucket], arr[j]);
    }

    int pos = 0;
    for (int[] bucket : counter) {
        for (int value : bucket) {
            arr[pos++] = value;
        }
    }
}</pre><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">locenco</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;locenco</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;zha***hong1206@gmail.com</p></div></span>3年前 (2020-09-23)</div></div></li><!-- #comment-## -->
<li class="comment odd alt thread-odd thread-alt depth-1" id="comment-57615"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;艾孜尔江</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;bju***ft@sina.com</p></div><div id="runoobvote-id-57615" data-commid = "57615" class="upvotejs"><a class="upvote"></a> <span class="count">14</span></div></div><div class="comt-main" id="div-comment-57615"><p>艾孜尔江补充使用C#基数排序算法如下:</p>

<pre>///基数排序
static void RadixSort(List&lt;int&gt; list)
{
    int maxValue = list.Max();//列表内部方法拿过来用用（在Linq中）
    int it = 0;//需要几趟
                //maxvalue 9-1 99-2 999-3
                //10^0&lt;=9 10^1&gt;9 it=1
                //10^0&lt;99 10^1&lt;99 10^2&gt;99 it=2
    while (Math.Pow(10, it) &lt;= maxValue)
    {
        List&lt;List&lt;int&gt;&gt; buckets = new List&lt;List&lt;int&gt;&gt;(10);//分10个桶对应0-9
        for (int i = 0; i &lt; 10; i++)
        {
            buckets.Add(new List&lt;int&gt;());
        }//列表初始化大小
        for (int i = 0; i &lt; list.Count; i++)//入桶
        {
            //989 it=0 989/10^it=989 989%10=9;
            int digit = (int)((list[i]) / (Math.Pow(10, it)) % 10);//得到对应桶
            buckets[digit].Add(list[i]);
        }//全部入桶
        list.Clear();//依次取出来
        for (int i = 0; i &lt; buckets.Count; i++)
        {
            list.AddRange(buckets[i]);
        }
        it += 1;//继续下一次循环入桶出桶
    }
}</pre><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">艾孜尔江</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;艾孜尔江</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;bju***ft@sina.com</p></div></span>3年前 (2020-10-08)</div></div></li><!-- #comment-## -->
<li class="comment even thread-even depth-1" id="comment-60433"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;奋斗的昌老师</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;153***7761@qq.com</p><p><i class="fa fa-external-link" aria-hidden="true"></i> <a rel="nofollow" target="_blank" href="https://blog.csdn.net/aninstein/article/details/112210927">&nbsp;&nbsp;参考地址</a></p></div><div id="runoobvote-id-60433" data-commid = "60433" class="upvotejs"><a class="upvote"></a> <span class="count">13</span></div></div><div class="comt-main" id="div-comment-60433"><p>补充一下python的基数排序代码实现：</p>

<pre>def radix_sort(data):

    if not data:
        return []
    max_num = max(data)  # 获取当前数列中最大值
    max_digit = len(str(abs(max_num)))  # 获取最大的位数

    dev = 1  # 第几位数，个位数为1，十位数为10&middot;&middot;&middot;
    mod = 10  # 求余数的除法
    for i in range(max_digit):
        radix_queue = [list() for k in range(mod * 2)]  # 考虑到负数，我们用两倍队列
        for j in range(len(data)):
            radix = int(((data[j] % mod) / dev) + mod)
            radix_queue[radix].append(data[j])

        pos = 0
        for queue in radix_queue:
            for val in queue:
                data[pos] = val
                pos += 1

        dev *= 10
        mod *= 10
    return data</pre>
<div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">奋斗的昌老师</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;奋斗的昌老师</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;153***7761@qq.com</p><p><i class="fa fa-external-link" aria-hidden="true"></i> <a rel="nofollow" target="_blank" href="https://blog.csdn.net/aninstein/article/details/112210927">&nbsp;&nbsp;参考地址</a></p></div></span>2年前 (2021-01-05)</div></div></li><!-- #comment-## -->
<li class="comment odd alt thread-odd thread-alt depth-1" id="comment-68288"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;秋月</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;luj***hneyiu1990@126.com</p></div><div id="runoobvote-id-68288" data-commid = "68288" class="upvotejs"><a class="upvote"></a> <span class="count">3</span></div></div><div class="comt-main" id="div-comment-68288"><p>go 的补一个吧:</p>

<pre>// 基数排序
func RadixSort(arr []int) {
    // 计算最长的数字
    var (
        maxVal int
        maxLen int
    )
    for _, v := range arr {
        if maxVal &lt; v {
            maxVal = v
        }
    }
    for maxVal &gt; 0 {
        maxLen++
        maxVal /= 10
    }

    // 循环进行数据分配与回归
    var (
        base    = 1           // 取余基数，初始是1，用于取出每个元素的倒数第 i+1 位的值，计算公式：v / base %10
        buckets = [10][]int{} // 基数桶，10个
    )
    for i := 0; i &lt; maxLen; i++ { // 遍历位
        for _, v := range arr { // 遍历数组
            d := v / base % 10                 // 每个数字当前位值
            buckets[d] = append(buckets[d], v) // 存入对应桶中
        }

        // 将桶中元素还原到arr
        idx := 0
        for x, bucket := range buckets {
            if len(bucket) == 0 {
                continue
            }

            for _, v := range bucket {
                arr[idx] = v
                idx++
            }

            // 桶清空
            buckets[x] = []int{}
        }

        base *= 10 // 基数*10
    }
}</pre><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">秋月</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;秋月</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;luj***hneyiu1990@126.com</p></div></span>1年前 (2021-11-18)</div></div></li><!-- #comment-## -->
<li class="comment even thread-even depth-1" id="comment-69043"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;柠檬茶</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;150***31468@163.com</p></div><div id="runoobvote-id-69043" data-commid = "69043" class="upvotejs"><a class="upvote"></a> <span class="count">3</span></div></div><div class="comt-main" id="div-comment-69043"><p>补上python的实现代码:</p>


<pre>def radixSort(nums):
    """
    基数排序，数组元素必须是正整数
    &gt;&gt;&gt;nums = [334, 5, 67, 345, 7, 99, 4, 23, 78, 45, 1, 3453, 23424]
    &gt;&gt;&gt;radixSort(nums)
    &gt;&gt;&gt;[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424]
    """
    #遍历数组获取数组最大值和最大值对应的位数
    maxValue = nums[0]
    for n in nums:
        maxValue = max(n, maxValue)
    #迭代次数
    iterCount = len(str(maxValue))
    for i in range(iterCount):
        #定义桶，大小为10，对应0-9
        bucket = [[] for _ in range(10)]
        for n in nums:
            index = (n//10**i)%10
            bucket[index].append(n)
        #nums数组清零，并合并桶内元素至nums
        nums.clear()
        for b in bucket:
            nums.extend(b)
        print(nums)
    return nums
nums = [334, 5, 67, 345, 7, 99, 4, 23, 78, 45, 1, 3453, 23424]
radixSort(nums)</pre><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">柠檬茶</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;柠檬茶</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;150***31468@163.com</p></div></span>1年前 (2021-12-18)</div></div></li><!-- #comment-## -->
<li class="comment odd alt thread-odd thread-alt depth-1" id="comment-71854"><span class="comt-f">#0</span><div class="comt-avatar wrapper"><i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i><div class="tooltip"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;散步留馨</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;she***nglife@163.com</p></div><div id="runoobvote-id-71854" data-commid = "71854" class="upvotejs"><a class="upvote"></a> <span class="count">3</span></div></div><div class="comt-main" id="div-comment-71854"><p>上面 Java 版本有点问题：</p>

<pre>for (int i = 0; i &lt; maxDigit; i++, dev *= 10, mod *= 10) {
    // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
    int[][] counter = new int[mod * 2][0];
....
}</pre>
<p>counter 数组的定义，会随着 mod 不断乘 10 变得越来越大。理论上 counter 数组只需要容量为 20 就可以表示负数与正数的所有数字字符。 </p>
<p>
另外，方法 getMaxDigit 计算数字的最大长度，只考虑到最大值的长度，没有考虑当存在负数时，最小值负数的字符长度也可能是最大的长度。</p>

<p>更新后的版本：</p>

<pre>/** 基数排序  */
public class RadixSort  {

  public int[] sort(int[] arr) {

    int maxDigit = getMaxDigit(arr);
    return radixSort(arr, maxDigit);
  }

  /**   * 获取最高位数   */  private int getMaxDigit(int[] arr) {
    int maxValue = getMaxValue(arr);
    int minValue = getMinValue(arr);
    return Math.max(getNumLength(maxValue), getNumLength(minValue));
  }

  private int getMaxValue(int[] arr) {
    int maxValue = arr[0];
    for (int value : arr) {
      if (maxValue &lt; value) {
        maxValue = value;
      }
    }
    return maxValue;
  }

  private int getMinValue(int[] arr) {
    int minValue = arr[0];
    for (int value : arr) {
      if (minValue &gt; value) {
        minValue = value;
      }
    }
    return minValue;
  }

  protected int getNumLength(long num) {
    if (num == 0) {
      return 1;
    }
    int lenght = 0;
    for (long temp = num; temp != 0; temp /= 10) {
      lenght++;
    }
    return lenght;
  }

  private int[] radixSort(int[] arr, int maxDigit) {
    int mod = 10;
    int dev = 1;

    for (int i = 0; i &lt; maxDigit; i++, dev *= 10, mod *= 10) {
      // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)      int[][] counter = new int[20][0];

      for (int j = 0; j &lt; arr.length; j++) {
        int bucket = ((arr[j] % mod) / dev) + 10;
        counter[bucket] = arrayAppend(counter[bucket], arr[j]);
      }

      int pos = 0;
      for (int[] bucket : counter) {
        for (int value : bucket) {
          arr[pos++] = value;
        }
      }
    }

    return arr;
  }

  /**   * 自动扩容，并保存数据   *   * @param arr   * @param value   */  private int[] arrayAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
  }
}</pre><div class="comt-meta wrapper"><span class="comt-author"><a target="_blank" href="javascript:;">散步留馨</a><div class="tooltip tooltip1"><p><i class="fa fa-user" aria-hidden="true"></i>&nbsp;&nbsp;&nbsp;散步留馨</p><p><i class="fa fa-envelope" aria-hidden="true"></i>&nbsp;&nbsp;she***nglife@163.com</p></div></span>1年前 (2022-04-13)</div></div></li><!-- #comment-## -->
	</ol>
	<div class="pagenav">
			</div>
</div>
<div id="respond" class="no_webshot"> 
		<div class="comment-signarea" style="display:none; padding: 20px 20px;"> 
	<h3 class="text-muted" id="share_code" style="color: #799961;"><i class="fa fa-pencil-square-o" aria-hidden="true"></i> 点我分享笔记</h3>
	<!--
	<p style="font-size:14px;">笔记需要是本篇文章的内容扩展！</p><br>
	<p style="font-size:12px;"><a href="../tougao" target="_blank">文章投稿，可点击这里</a></p>
	<p style="font-size:14px;"><a href="../w3cnote/runoob-user-test-intro.html#invite" target="_blank">注册邀请码获取方式</a></p>
		<h3 class="text-muted"><i class="fa fa-info-circle" aria-hidden="true"></i> 分享笔记前必须<a href="javascript:;" class="runoob-pop">登录</a>！</h3>
		<p><a href="../w3cnote/runoob-user-test-intro.html#invite" target="_blank">注册邀请码获取方式</a></p>-->
	</div>
		
	<form action="/wp-content/themes/runoob/option/addnote.php" method="post" id="commentform" style="display:none;">
		<div class="comt">
			<div class="comt-title">
				<i style="font-size:36px;" class="fa fa-user-circle" aria-hidden="true"></i>				<p><a id="cancel-comment-reply-link" href="javascript:;">取消</a></p>
			</div>
			<div class="comt-box">
			<div id="mded"></div>
			
				<div class="comt-ctrl">
					<div class="comt-tips"><input type='hidden' name='comment_post_ID' value='21445' id='comment_post_ID' />
<input type='hidden' name='comment_parent' id='comment_parent' value='0' />
</div>
					<button type="submit" name="submit" id="submit" tabindex="5"><i class="fa fa-pencil" aria-hidden="true"></i> 分享笔记</button>
				</div>
			</div>
		
				
					<div class="comt-comterinfo"> 
						<ul id="comment-author-info">
							<li class="form-inline"><label class="hide" for="author">昵称</label><input class="ipt" type="text" name="author" id="author" value="" tabindex="2" placeholder="昵称"><span class="text-muted">昵称 (必填)</span></li>
							<li class="form-inline"><label class="hide" for="email">邮箱</label><input class="ipt" type="text" name="email" id="email" value="" tabindex="3" placeholder="邮箱"><span class="text-muted">邮箱 (必填)</span></li>
							<li class="form-inline"><label class="hide" for="url">引用地址</label><input class="ipt" type="text" name="url" id="url" value="" tabindex="4" placeholder="引用地址"><span class="text-muted">引用地址</span></li>
						</ul>
					</div>
				
			
		</div>

	</form>
	</div>
<script type="text/javascript">
$(function() {
	//初始化编辑器
	
	var editor = new Simditor({
	  textarea: $('#mded'),
	  placeholder: '写笔记...',
	  upload:false,
	 // upload: {url:'/api/comment_upload_file.php',params: null,fileKey: 'upload_file',connectionCount: 1,leaveConfirm: '文件正在上传，您确定离开?'},
	  defaultImage: 'https://www.runoob.com/images/logo.png',
	  codeLanguages: '',
	  autosave: 'editor-content',
	  toolbar: [  'bold','code','ul','ol','image' ]
	});
	editor.on('selectionchanged', function() {
		$(".code-popover").hide();
	});

	// 提交数据
	$("#share_code").click(function() {
		$(".comment-signarea").hide();
		$("#commentform").show();
		
	});
	$("#user_add_note").click(function() {
		$(".comment-signarea").hide();
		$("#commentform").show();
		$('html, body').animate({
       	    scrollTop: $("#respond").offset().top
    	}, 200);
	});

	// 提交笔记
	var commentform=$('#commentform');
	commentform.prepend('<div id="comment-status" style="display:none;" ></div>');
	var statusdiv=$('#comment-status');
	
	commentform.submit(function(e){
		e.preventDefault();
		var noteContent = editor.getValue();
		// console.log(noteContent);
		noteContent = noteContent.replace(/<pre><code>/g,"<pre>");
		noteContent = noteContent.replace(/<\/code><\/pre>/g,"</pre>");
		
		// 系列化表单数据
		var comment_parent = 0;
		var is_user_logged_in = $("#is_user_logged_in").val();
		var comment_post_ID =  21445;
		var _wp_unfiltered_html_comment = $("#_wp_unfiltered_html_comment").val();
		var comment = noteContent;
		var author = $("#author").val();
		var url = $("#url").val();
		var email = $("#email").val();
		if(isBlank(author) && is_user_logged_in==0) {
			statusdiv.html('<p  class="ajax-error">请输入昵称！</p>').show();
		} else if(isBlank(email)  && is_user_logged_in==0) {
			statusdiv.html('<p  class="ajax-error">请输入邮箱！</p>').show();
		} else {
			// var formdata=commentform.serialize() + "&comment=" + noteContent ;
			// 添加状态信息
			statusdiv.html('<p>Processing...</p>').show();
			// 获取表单提交地址
			var formurl=commentform.attr('action');
			
			// 异步提交
			$.ajax({
					type: 'post',
					url: formurl,
					dataType:'json',
					data: {"comment_parent":comment_parent,"comment_post_ID":comment_post_ID, "_wp_unfiltered_html_comment":_wp_unfiltered_html_comment,"comment":comment,"url":url, "email":email,"author":author},
					error: function(XMLHttpRequest, textStatus, errorThrown){
					statusdiv.html('<p class="ajax-error" >数据不完整或表单提交太快了！</p>').show();
				},
				success: function(data, textStatus){
					if(data.errorno=="0") {
						$("#submit").prop('disabled', true);
						statusdiv.html('<p class="ajax-success" >笔记已提交审核，感谢分享笔记！</p>').show();
						alert('笔记已提交审核，感谢分享笔记！');
					}else{
						statusdiv.html('<p class="ajax-error" >'+data.msg+'</p>').show();
					}
					commentform.find('textarea[name=comment]').val('');
				}
			});
			setTimeout(function(){
		        $("#submit").prop('disabled', false);
		    }, 10*1000);
		}
		return false;

	});
	$(".comt-author").click(function() {
		href = $(this).children("a").attr("href");
		if(href.indexOf("/note/")!=-1) {
			var win = window.open(href, '_blank');
  			win.focus();
		}
	});
	$(".comt-meta span").hover(function(){
		$(this).children(".tooltip").css({ "opacity": 1, "pointer-events": "auto"});
	},function(){
		$(this).children(".tooltip").removeAttr("style");
	});
	/*
	$(".wrapper i").hover(function(){
		$(this).siblings(".tooltip").css({ "opacity": 1, "pointer-events": "auto"});
	},function(){
		$(this).siblings(".tooltip").css({ "opacity": 0, "pointer-events": "auto"});
	});
	*/
	//Upvote.create('runoobvote-id', {callback: vote_callback});
	var ajaxurl = 'https://www.runoob.com/wp-admin/admin-ajax.php';
	var callback = function(data) {
		//console.log($('#runoobvote-id').upvote('upvoted'));
		//console.log($('#runoobvote-id').upvote('downvoted'));
		//console.log(data);
		_vote_action = data.action;
		id_arr = data.id.split('-');
		um_id= id_arr[2];
		//console.log(um_id);
		
		var re = /^[1-9]+/;
		if (re.test(um_id)) { 
			var ajax_data = {
				_vote_action: _vote_action,
				action: "pinglun_zan",
				um_id: um_id,
				um_action: "ding"
			};
			//console.log(ajax_data);
			$.post(ajaxurl,ajax_data,function(status){
				//if(status.vote_num>999) {
				//	_voteHtml = '<span style="display: block; text-align: center;font-size: 20px; color: #6a737c; margin: 8px 0;">'+kFormatter(status.vote_num) +'</span>';
				//	$("#runoobvote-id-" + um_id + " .count").hide().after(_voteHtml);
				//}
				
			});
		}
	};
	if($('#comments').length && $('.upvotejs').length){
		$('.upvotejs').upvote({id: 21445, callback: callback});
	
		$.post(ajaxurl,{"action":"pinglun_zan","postid":21445},function(data){  
			$(data).each(function(key,value) {
				$("#runoobvote-id-" + value.commid + " .upvote").addClass(value.upvotejs_class);
				$("#runoobvote-id-" + value.commid + " .downvote").addClass(value.downvote_class);
				$("#runoobvote-id-" + value.commid + " .count").text(value.upvote_count);
			})
		},'json');
		
	}
	
	
});
function isBlank(str) {
    return (!str || /^\s*$/.test(str));
}
function kFormatter(num) {
	// return num;
    return Math.abs(num) > 999 ? Math.sign(num)*((Math.abs(num)/1000).toFixed(1)) + 'k' : Math.sign(num)*Math.abs(num)
}

</script>

<link rel="stylesheet" href="../0/qa.css?1.44">
<link rel="stylesheet" type="text/css" href="../0/simditor.min.css" />
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
<script type="text/javascript" src=""></script>
			<div class="article-heading-ad" id="w3cnote-ad728">
			<script async src=""></script>
			<!-- 移动版 自动调整 -->
			<ins class="adsbygoogle"
			     style="display:inline-block;min-width:300px;max-width:970px;width:100%;height:90px"
			     data-ad-client="ca-pub-5751451760833794"
			     data-ad-slot="1691338467"
			     data-ad-format="horizontal"></ins>
			<script>
			(adsbygoogle = window.adsbygoogle || []).push({});
			</script>
			</div>
			<style>
@media screen and (max-width: 768px) {
	#w3cnote-ad728 {
		display: none;
	}
}
p.note-author {
    border-bottom: 1px solid #ddd;
    font-size: 18px;
    font-weight: bold;
    color: #78a15a;
    padding-bottom: 2px;
    margin-bottom: 4px;
}
</style>
<script>
var aid = 21445;
</script>
	</div>
		
	</div>
	<div class="listcol last right-column">

	<script type="text/javascript">
jQuery(document).ready(function ($){
	var total = $(".membership li").length;
	var left_list = '';
	href = window.location.href;
	
	$(".membership li").each(function(index, value){

		left_list += $(this).html();

		cur_href = $(this).find("a").attr("href");
		cur_obj = $(this);
		
		if(href.match(cur_href) != null) {
			if(index==0) {
				$(".previous-design-link").hide();
			}
			if(index==(total-1)) {
				$(".next-design-link").hide();
			}
			prev_href = cur_obj.prev("li").find("a").attr("href");
			prev_title = cur_obj.prev("li").find("a").attr("title");

			next_href = cur_obj.next("li").find("a").attr("href");
			next_title = cur_obj.next("li").find("a").attr("title");
			if(prev_title) {
				$(".previous-design-link a").attr("href", prev_href);
				$(".previous-design-link a").attr("title", prev_title);
				$(".previous-design-link a").text(prev_title);
			} else {
				$(".previous-design-link").html("");
			}

			if(next_title) {
				$(".next-design-link a").attr("href", next_href);
				$(".next-design-link a").attr("title", next_title);
				$(".next-design-link a").text(next_title);
			} else {
				$(".next-design-link").html("");
			}
		}
	});

	$("#leftcolumn").html(left_list);
});
	</script>
	<div class="sidebar-box cate-list">
	<div class="sidebar-box recommend-here list-link">
	<a href="javascript:void(0);">算法系列</a>	</div>
	
	<ul class="membership">
		
	<li><a target="_top" data-id="21423" title="1.0 十大经典排序算法" href="../w3cnote/ten-sorting-algorithm.html" >1.0 十大经典排序算法</a></li>
	
		
	<li><a target="_top" data-id="21425" title="1.1 冒泡排序" href="../w3cnote/bubble-sort.html" >1.1 冒泡排序</a></li>
	
		
	<li><a target="_top" data-id="21427" title="1.2 选择排序" href="../w3cnote/selection-sort.html" >1.2 选择排序</a></li>
	
		
	<li><a target="_top" data-id="21429" title="1.3 插入排序" href="../w3cnote/insertion-sort.html" >1.3 插入排序</a></li>
	
		
	<li><a target="_top" data-id="21431" title="1.4 希尔排序" href="../w3cnote/shell-sort.html" >1.4 希尔排序</a></li>
	
		
	<li><a target="_top" data-id="21433" title="1.5 归并排序" href="../w3cnote/merge-sort.html" >1.5 归并排序</a></li>
	
		
	<li><a target="_top" data-id="21435" title="1.6 快速排序" href="../w3cnote/quick-sort-2.html" >1.6 快速排序</a></li>
	
		
	<li><a target="_top" data-id="21437" title="1.7 堆排序" href="../w3cnote/heap-sort.html" >1.7 堆排序</a></li>
	
		
	<li><a target="_top" data-id="21440" title="1.8 计数排序" href="../w3cnote/counting-sort.html" >1.8 计数排序</a></li>
	
		
	<li><a target="_top" data-id="21442" title="1.9 桶排序" href="../w3cnote/bucket-sort.html" >1.9 桶排序</a></li>
	
		<li>
	1.10 基数排序	</li>
	
	</ul></div>	</div>
</div>


<!-- 底部 -->
<div id="footer" class="mar-t50">
   <div class="runoob-block">
    <div class="runoob cf">
     <dl>
      <dt>
       在线实例
      </dt>
      <dd>
       &middot;<a target="_blank" href="../html/html-examples.html">HTML 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../css/css-examples.html">CSS 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../js/js-examples.html">JavaScript 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../ajx/ajax-examples.html">Ajax 实例</a>
      </dd>
       <dd>
       &middot;<a target="_blank" href="../jquery/jquery-examples.html">jQuery 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../xml/xml-examples.html">XML 实例</a>
      </dd>
      <dd>
       &middot;<a target="_blank" href="../java/java-examples.html">Java 实例</a>
      </dd>
     
     </dl>
     <dl>
      <dt>
      字符集&工具
      </dt>
      <dd>
       &middot; <a target="_blank" href="../charsets/html-charsets.html">HTML 字符集设置</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="../tags/html-ascii.html">HTML ASCII 字符集</a>
      </dd>
     <dd>
       &middot; <a target="_blank" href="https://c.runoob.com/front-end/6939/">JS 混淆/加密</a>
      </dd> 
      <dd>
       &middot; <a target="_blank" href="https://c.runoob.com/front-end/6232/">PNG/JPEG 图片压缩</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="../tags/html-colorpicker.html">HTML 拾色器</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="..//c.runoob.com/front-end/53">JSON 格式化工具</a>
      </dd>
      <dd>
       &middot; <a target="_blank" href="..//c.runoob.com/front-end/6680/">随机数生成器</a>
      </dd>
     </dl>
     <dl>
      <dt>
       最新更新
      </dt>
                   <dd>
       &middot;
      <a href="../matplotlib/matplotlib-imread.html" title="Matplotlib imread() 方法">Matplotlib imre...</a>
      </dd>
              <dd>
       &middot;
      <a href="../matplotlib/matplotlib-imsave.html" title="Matplotlib imsave() 方法">Matplotlib imsa...</a>
      </dd>
              <dd>
       &middot;
      <a href="../matplotlib/matplotlib-imshow.html" title="Matplotlib imshow() 方法">Matplotlib imsh...</a>
      </dd>
              <dd>
       &middot;
      <a href="../matplotlib/matplotlib-hist.html" title="Matplotlib 直方图">Matplotlib 直方图</a>
      </dd>
              <dd>
       &middot;
      <a href="../python3/python-func-object.html" title="Python object() 函数">Python object()...</a>
      </dd>
              <dd>
       &middot;
      <a href="../python3/python-ai-draw.html" title="Python AI 绘画">Python AI 绘画</a>
      </dd>
              <dd>
       &middot;
      <a href="../w3cnote/cursor-editor.html" title="神辅助 Cursor 编辑器，加入 GPT-4 让编码更轻松！">神辅助 Cursor ...</a>
      </dd>
             </dl>
     <dl>
      <dt>
       站点信息
      </dt>
      <dd>
       &middot;
       <a target="_blank" href="mailto:admin@runoob.com" rel="external nofollow">意见反馈</a>
       </dd>
      <dd>
       &middot;
      <a target="_blank" href="../disclaimer">免责声明</a>
       </dd>
      <dd>
       &middot;
       <a target="_blank" href="../aboutus">关于我们</a>
       </dd>
      <dd>
       &middot;
      <a target="_blank" href="../archives">文章归档</a>
      </dd>
    
     </dl>
    
     <div class="search-share">
      <div class="app-download">
        <div>
         <strong>关注微信</strong>
        </div>
      </div>
      <div class="share">
      <img width="128" height="128" src="/wp-content/themes/runoob/assets/images/qrcode.png" />
       </div>
     </div>
     
    </div>
   </div>
   <div class="w-1000 copyright">
     Copyright &copy; 2013-2023    <strong><a href="../" target="_blank">菜鸟教程</a></strong>&nbsp;
    <strong><a href="../" target="_blank">runoob.com</a></strong> All Rights Reserved. 备案号：<a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn/">闽ICP备15012807号-1</a>
   </div>
  </div>
  <div class="fixed-btn">
    <a class="go-top" href="javascript:void(0)" title="返回顶部"> <i class="fa fa-angle-up"></i></a>
    <a class="qrcode"  href="javascript:void(0)" title="关注我们"><i class="fa fa-qrcode"></i></a>
    <a class="writer" style="display:none" href="javascript:void(0)"   title="标记/收藏"><i class="fa fa-star" aria-hidden="true"></i></a>
    <!-- qrcode modal -->
    <div id="bottom-qrcode" class="modal panel-modal hide fade in">
      <h4>微信关注</h4>
      <div class="panel-body"><img alt="微信关注" width="128" height="128" src="/wp-content/themes/runoob/assets/images/qrcode.png"></div> 
    </div>
  </div>

 <div style="display:none;">
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-84264393-2"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-84264393-2');
</script>
<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "https://hm.baidu.com/hm.js?3eec0b7da6548cf07db3bc477ea905ee";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>

</div>
<script>
window.jsui={
    www: 'https://www.runoob.com',
    uri: 'https://www.runoob.com/wp-content/themes/runoob'
};
</script>

<script src=""></script>
<script src=""></script>

</body>
</html>